Cream of the Crop 1/Cream of the Crop 1.iso/PROGRAM/WLIST.ARJ/LINKLIST.DOC

Text File | 1992-05-16 | 10KB | 352 lines

Linked List Library Documentation

February 22, 1991
May 15, 1992 (minor tweaks)

by Paul Wheaton

To make these libraries available, you need to include <LinkList.h>
and link with LinkList.obj.

1    what is a linked list:  help for the heapless
1.1    some references
1.2    my version
2    LinkedList class
2.01    Root()
2.02    Cur()
2.03    Size()
2.04    Top()
2.05    Num()
2.06    Next()
2.07    Prev()
2.08    Last()
2.09    Insert()
2.10    Add()
2.11    Append()
2.12    Push()
2.13    DelCur()
2.14    DelCurObj()
2.15    Pop()
2.16    operator[]
3    custom linked list classes
4    Stack class
5    Queue class



1 what is a linked list:  help for the heapless

1.1 some references

  Perhaps the best way to learn about linked lists is to go one of the
  foremost authorities:  In the book "Algorithms + Data Structures =
  Programs" by Niklaus Wirth (1976 Prentice-Hall) in the chapter
  "Dynamic Information Structures" under the section "Linear Lists" is
  a complete tutorial.

  The book "Structure and Interpretation of Computer Programs" by
  Abelson, Sussman and Sussman (1985 MIT Press) is based on the Scheme
  language (a LISP dialect) so it's just thick with list stuff.
  Section 2.2.1 should give you a good idea of what's going on here.

  The book "An Introduction to Object Oriented Programming and C++" by
  Wiener and Pinson (1988 Addison-Wesley) has the only decent C or C++
  linked list reference I could find inside half an hour.  See section
  6.2: "An Object-Oriented Solution to Generating a Linked List"

1.2 my version

  I'm going to assume that you have a pretty good grip on what a heap
  is:  that dynamic memory thing.

  Let's say that you have a structure called a DooDad that takes up
  about a thousand bytes.  Let's also say that you need to keep about
  a hundred of them, ordered, in memory for the sake of speed.  Part
  of what the user will be doing with this list is changing the order
  of it.

  If you wanted to do a malloc() to store all of this stuff, you'd
  have to ask for about 100,000 bytes.  More than Microsoft C can
  handle in one malloc.  Even if you could get that much memory,
  what's going to happen when you try to move a DooDad from the middle
  and put it at the beginning?  A whole lot of time consuming memory
  copying, that's what (e.g. make a 1000 byte temp copy of element 50;
  shift about 50,000 bytes about 1000 bytes to the right; copy your
  temp to the beginning of your data area).  If you had to insert and
  delete DooDads a lot, things could be unbearably slow.

  Now for a linked list approach.  With a tiny struct

    struct Node
      {
        Node* PrevNode;
        DooDad* Dat;
        Node* NextNode;
      };

  and by allocating memory for your DooDads in thousand byte chunks,
  you can create a list like this:










      xxx picture goes here










  To move a DooDad from the middle and put it at the beginning, change
  six pointers.










      xxx picture goes here










  Voila'!  Everything just the way you want it and without all that
  copying stuff.  The second diagram might look a little gross, but
  inside of the computer it looks just as nice as the first one.  If
  you want, the second diagram can be redrawn to look just like the
  first.

  Linked lists are also good for bunches of different sized objects.

2 LinkedList class

  This linked list class currently uses the model described above.
  Sometimes called a "doubly linked list with nodes", the "doubly"
  referring to the fact that the list has "previous" pointers as well
  as "next" pointers.  The "nodes" part refers to the pointers being
  in its own record and not part of the data record.

  There is only one way to create a LinkedList object.  With
  absolutely no parameters (e.g. "LinkedList L;").  When you add any
  data to the list, you must create your data yourself and simply pass
  in a pointer to your data.  You are welcome to add data that is on
  the heap, the stack (local variables or parameters) or the data
  segment (global data).  If you want to add the same object several
  times, you'll just have several nodes pointing to the same place.

  When the list is deleted or goes out of scope, it will delete any
  nodes that may still be active.  It will not delete any data that
  you have connected to the list.

  All of the pointers are of type "void*".

2.01 Root()

  Prototype:  void* Root()

  The "current pointer" is changed to point to the last element in the
  list and then the new "current pointer" is returned. Returns NULL if
  there are no elements.

2.02 Cur()

  Prototype:  void* Cur()

  Returns a pointer to the current element.  Returns NULL if there
  are no elements.

2.03 Size()

  Prototype:  Long Size()

  Returns the number of elements in the list.

2.04 Top()

  Prototype:  Long Top()

  Returns the index to the last element.  Equivalent to Size()-1.

2.05 Num()

  Prototype:  Long Num()

  Returns the index to the current element.  Would be any number from
  0 to Top().

2.06 Next()

  Prototype:  void* Next()

  The Cur() pointer is changed to point to the next element in the
  list and then the new Cur() is returned.  Returns NULL if there are
  no elements.

2.07 Prev()

  Prototype:  void* Prev()

  The Cur() pointer is changed to point to the previous element in the
  list and then the new Cur() is returned.  Returns NULL if there are
  no elements.

2.08 Last()

  Prototype:  void* Last()

  The Cur() pointer is changed to point to the last element in the
  list and then the new Cur() is returned.  Returns NULL if there are
  no elements.

2.09 Insert()

  Prototype:  Bool Insert(void* NewRec)

  Will insert a new node between the previous element and the current
  element.  On exit, Cur() will point to NewRec.  Returns False if
  there was not enough memory to create a new node.

2.10 Add()

  Prototype:  Bool Add(void* NewRec)

  Will insert a new node between the current element and the next
  element.  On exit, Cur() will point to NewRec.  Returns False if
  there was not enough memory to create a new node.

2.11 Append()

  Prototype:  Bool Append(void* NewRec)

  Will stick a new node on the end of the list. On exit, Cur() will
  point to NewRec.  Returns False if there was not enough memory to
  create a new node.

2.12 Push()

  Prototype:  Bool Push(void* NewRec)

  Will stick a new node on the end of the list. On exit, Cur() will
  point to NewRec.  Returns False if there was not enough memory to
  create a new node.

  Note that this works the same way as Append().  This function is
  provided for clarity in your code when you wish to use a linked list
  like a stack (see the Pop() function).

2.13 DelCur()

  Prototype:  void DelCur()

  I recommend that if this node points to data on the heap (as is most
  often the case) that you should first remove your data from the heap
  using the Cur() pointer.

  This function will remove the current node from the list.  It will
  *not* do anything to the data.  On exit, Cur() will point to what
  would have been pointed to by Next().

2.14 DelCurObj()

  Prototype:  void DelCurObj()

  This function will attempt to "delete" your data.  This will only
  work on data that has been created with "new" and does not have a
  destructor.  After this, it will remove the current node from the
  list. On exit, Cur() will point to what would have been pointed to
  by Next().

2.15 Pop()

  Prototype:  void* Pop()

  This function will delete the last node in the list and return a
  pointer to what that node pointed to.  On exit Cur() will point to
  the new last element.

2.16 operator[]

  Prototype:  void* operator[](Long Index)

  This operator will allow your linked list to be treated like an
  array.  If you want a pointer to the fifth element of your
  LinkedList name "L", simply use "L[4]".  A valid function call would
  be something like "memcpy(L[2],L[8],400);".  On exit, Cur() will
  point to the same place.

3 custom linked list classes

  A problem with the LinkedList class is that it will only deal with
  void pointers.  That means that if you want to reference a field of
  a struct in a LinkedList, you will first have to take the pointer it
  gives you and cast it to be a pointer to your object and then
  de-reference a field.  What a hassle!  For example:

    struct FooType
      {
        Char Name[40];
        Long SSN;
        Long BirthYear;
      };

    void Bar()
      {
        LinkedList L;
        L.Add(new FooType);
        strcpy(((FooType*)L.Cur())->Name,"Bob");
        ((FooType*)L.Cur())->SSN=123456789;
        ((FooType*)L.Cur())->BirthYear=1954;
      }

  Using the same FooType struct, we could have

    CreateLinkedListClass(FooList,FooType);

    void Bar()
      {
        FooList L;
        L.Add(*new FooType);
        strcpy(L.Cur().Name,"Bob");
        L.Cur().SSN=123456789;
        L.Cur().BirthYear=1954;
      }

  Note that all the parameters in your custom class accept and return
  references instead of pointers.

4 Stack class

  The Stack class works exactly the same as the LinkedList class.
  This class is provided for readability's sake only.  If you intend
  to use your linked lisk like a stack, you might want to declare it
  as "Stack FooStack;" rather than "LinkedList FooStack;"

5 Queue class

  This class works exactly the same as the LinkedList class *except*
  for the Pop() function.  Pop() will delete the first node in the list
  and return a pointer to what that node pointed to.  On exit Cur()
  will point to the new first element.  So now you see how it behaves
  like a Queue instead of a Stack:  You Push() stuff onto the top and
  Pop() them off the bottom.